package com.aqie.medium.trie;

import com.aqie.medium.structure.Trie;

import java.util.HashSet;
import java.util.Set;

/**
 * 421 数组中两个数最大异或值
 * 给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。
 *
 * 找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i,  j < n 。
 *
 */
public class FindMaximumXOR {
    /**
     * 简单粗暴 直接循环
     * @param nums
     * @return
     */
    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j < nums.length; j++)
            if (ans < (nums[i] ^ nums[j])) ans = (nums[i] ^ nums[j]);
        }
        return ans;
    }


    /**
     * 异或性质 + 贪心算法
     * @param nums
     * @return
     */
    public int findMaximumXOR2(int[] nums) {
        int res = 0;
        int mask = 0;
        // 1. 保留前缀
        for (int i = 31; i >= 0; i--) {
            // 或者 mask = mask ^ (1 << i);
            mask = mask | (1 << i);

            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                // 2，保留前缀(从高位到低位)
                set.add(num & mask);
            }

            // 假设第n位为1， 前 n-1位res 为之前迭代求得
            int temp = res | (1 << i);
            for (Integer prefix : set) {
                if (set.contains(prefix ^ temp)) {
                    res = temp;
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 前缀树
     * @param nums
     * @return
     */
    public int findMaximumXOR3(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        Trie trie = new Trie();
        for (int num : nums) {
            trie.insert(num);
        }

        Trie.TrieNode cur = trie.root;
        while (cur.one == null || cur.zero == null) {
            cur = cur.zero != null ? cur.zero : cur.one;
        }
        return trie.searchXor(cur.one, cur.zero);

    }

    public static void main(String[] args) {
        int[] arr = {3, 10, 5, 25, 2, 8};
        for (int i = 0; i < arr.length; i++){
            for (int j = i + 1; j < arr.length;j++){
                System.out.println(arr[i] + " " + arr[j]);
            }
        }
    }
}
